package com.hanxiaozhang.no10leetcode.dynamicprogramming;

import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * 实例1:
 * 输入: "(()"
 * 输出: 2
 * 解释: 最长的有效括号子字符串是"()"
 * <p>
 * 实例2:
 * 输入: ")()())"
 * 输出: 4
 * 解析: 最长的有效括号子字符串是"()()"
 * <p>
 * 实例3：
 * 输入："()(()"
 * 输出：2
 * <p>
 * 挺难的，想出来这种思路
 *
 * @author hanxinghua
 * @create 2024/2/22
 * @since 1.0.0
 */
public class No32LongestValidParentheses {

    public static void main(String[] args) {

        String str1 = "(()";
        System.out.println(method1(str1));

        String str2 = ")()())";
        System.out.println(method1(str2));

    }

    /**
     * 方法1：使用栈方式
     * <p>
     * 利用栈的原理，首先我们遍历字符串，当遇到左括号'('时，将其所在位置的下标值放入栈中。当遇到右括号')'，首先取出栈顶元素，
     * 然后，用当前右括号的下标值减去当前栈顶元素的下标值。
     * <p>
     * 解释：这里是利用了下标值对长度进行计算，首先栈的原理不用多讲，我们只将左括号放入栈中，当遇到右括号时，如果栈中此时还有元素，
     * 说明栈顶的左括号与当前的右括号是一对，先将栈顶的元素取出。
     * 然后，用当前右括号的下标值减去栈顶元素(即上一个左括号)的下标值，得到的值就是格式正确的子字符串长度。
     * 通俗点来说就是把已经成对出现的左括号取走，那么现在栈里剩下的都是未匹配的左括号，已成对的右括号减去未成对的左括号，
     * 得到的值就是当前正对出现的左右括号的长度。以此类推，遍历结束后取最大值即可。注意一些边界值和栈的空判断。
     *
     * @param s
     * @return
     */
    public static int method1(String s) {
        int max = 0;
        if (s == null || s.isEmpty()) {
            return max;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(i);
            } else {
                stack.pop();
                // c is not '(' and stack is empty means string is start with n ')'
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    max = Math.max(i - stack.peek(), max);
                }
            }
        }
        return max;
    }




    /**
     * 方法二：动态规划 ，有时间再研究
     *
     * @param s
     * @return
     */
    public int method2(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        int max = 0;
        int[] dp = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2;
                }
                max = Math.max(max, dp[i]);
            }
        }
        return max;
    }

}
